package com.wengu.algorithm.controller;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;

public class TestController {

    // 使用缓存避免重复计算阶乘
    private static final BigInteger[] FACTORIAL_CACHE = new BigInteger[100];
    static {
        FACTORIAL_CACHE[0] = BigInteger.ONE;
        FACTORIAL_CACHE[1] = BigInteger.ONE;
    }

    // 使用组合数缓存
    private static final BigInteger[][] COMBINATION_CACHE = new BigInteger[100][100];

    private BigDecimal calculateA(int k, double successProb) {
        if (k < 0) {
            return BigDecimal.ZERO;
        }
        if (k == 0) {
            return new BigDecimal("0.5");
        }
        // 使用高精度计算避免浮点误差累积
        BigDecimal p = BigDecimal.valueOf(successProb);
        BigDecimal q = BigDecimal.ONE.subtract(p);

        BigDecimal sum = BigDecimal.ZERO;
        int start = (k % 2 == 1) ? (k + 1) / 2 : k / 2 + 1;

        // 预计算幂次，避免重复计算
        BigDecimal[] pPowers = new BigDecimal[k + 1];
        BigDecimal[] qPowers = new BigDecimal[k + 1];
        pPowers[0] = BigDecimal.ONE;
        qPowers[0] = BigDecimal.ONE;

        for (int i = 1; i <= k; i++) {
            pPowers[i] = pPowers[i - 1].multiply(p, MathContext.DECIMAL128);
            qPowers[i] = qPowers[i - 1].multiply(q, MathContext.DECIMAL128);
        }

        for (int r = start; r <= k; r++) {
            BigInteger comb = combination(k, r);
            BigDecimal term = new BigDecimal(comb)
                    .multiply(pPowers[r], MathContext.DECIMAL128)
                    .multiply(qPowers[k - r], MathContext.DECIMAL128);
            sum = sum.add(term, MathContext.DECIMAL128);
        }

        if (k % 2 == 0) {
            BigInteger comb = combination(k, k / 2);
            BigDecimal midTerm = new BigDecimal(comb)
                    .multiply(pPowers[k / 2], MathContext.DECIMAL128)
                    .multiply(qPowers[k / 2], MathContext.DECIMAL128);
            sum = sum.add(midTerm.multiply(new BigDecimal("0.5"), MathContext.DECIMAL128));
        }

        return sum;
    }

    private BigInteger combination(int n, int k) {
        if (k < 0 || k > n) {
            return BigInteger.ZERO;
        }
        if (k == 0 || k == n) {
            return BigInteger.ONE;
        }

        // 使用缓存
        if (COMBINATION_CACHE[n][k] != null) {
            return COMBINATION_CACHE[n][k];
        }

        // 使用更高效的组合数计算方法，避免大数阶乘
        k = Math.min(k, n - k); // 利用对称性减少计算量
        BigInteger result = BigInteger.ONE;

        for (int i = 1; i <= k; i++) {
            result = result.multiply(BigInteger.valueOf(n - k + i))
                    .divide(BigInteger.valueOf(i));
        }

        COMBINATION_CACHE[n][k] = result;
        return result;
    }

    public BigInteger factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative, but got " + n);
        }

        // 使用缓存
        if (n < FACTORIAL_CACHE.length && FACTORIAL_CACHE[n] != null) {
            return FACTORIAL_CACHE[n];
        }

        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }

        if (n < FACTORIAL_CACHE.length) {
            FACTORIAL_CACHE[n] = result;
        }
        return result;
    }

    public BigDecimal calculateA2(int k,double successProb) {
        if (k <= 0) {
            return BigDecimal.ZERO;
        }
        BigDecimal sum = BigDecimal.ZERO;
        int start = (k % 2 == 1) ? (k+1)/2 : k/2 + 1;

        for (int r = start; r <= k; r++) {
            BigInteger comb = combination(k, r);
            sum = sum.add(new BigDecimal(comb).multiply(BigDecimal.valueOf(Math.pow(successProb, r))).multiply(BigDecimal.valueOf(Math.pow(1- successProb, k-r))));
        }

        if (k % 2 == 0) {
            BigDecimal midTerm = new BigDecimal(combination(k, k/2)).multiply(
                    BigDecimal.valueOf(Math.pow(successProb, k / 2))).multiply(BigDecimal.valueOf(Math.pow(1 - successProb, k / 2)));
            sum = sum.add(new BigDecimal("0.5").multiply(midTerm));
        }
        return sum;
    }

    private BigDecimal calculateF(int k,double successProb) {
        // 根据公式(2)实现F计算
        if (k % 2 == 1 || k == 0) {
            return calculateA(k,successProb);
        } else {
            return (calculateA(k-1,successProb).add(calculateA(k+1,successProb)).divide(new BigDecimal("2")));
        }
    }

    public static void main(String[] args) {
        TestController test = new TestController();
        for (int i = 0; i < 10; i++) {
            long startTime = System.nanoTime();
            BigDecimal result = test.calculateF(i, 0.9);
            long endTime = System.nanoTime();
            System.out.println("i=" + i + ", result=" + result.doubleValue() +
                    ", time=" + (endTime - startTime) + "ns");
        }
    }
}
